import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2024-11-13
 * Time:11:14
 */
public class Sort {
    //直接插入排序
    public static void insterSort(int[] array) {
        int i = 1;
        int j = i - 1;
        for (i = 1; i < array.length; i++) {
            int tmp = array[i];//会随着插入的元素改变
            for (j = i - 1; j >= 0; j--) {
                //插入的元素比j小
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            //插入的元素比j大
            array[j + 1] = tmp;
        }
    }

    //希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
        shell(array, gap);//此时进行以后一趟排序gap为1.也可以忽略
        //因为此时已经有序
    }

    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];//会随着插入的元素改变
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                //插入的元素比j小
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            //插入的元素比j大
            array[j + gap] = tmp;
        }
    }

    //选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            if (maxIndex == left) {
                maxIndex = minIndex;//不交换
            }
            swap(array, right, maxIndex);
            left++;
            right--;
        }
    }

    //堆排序
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }

    //建大堆
    private static void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    //向下建堆
    private static void shiftDown(int[] array, int parent, int end) {
        int child = 2 * parent + 1;
        while (child < end) {
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            if (flg == false) {
                return;
            }
        }
    }

    //快速排序
    //hoare
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    //递归左右
    private static void quick(int[] array, int start, int end) {
        if (start >= end) {//左边是一个节点，或者一个节点也没有
            return;
        }
        if (end - start + 1 <= 15) {
            //插入排序
            insterSortRange(array, start, end);
            return;
        }
        //三数取中
        int index = midOfThree(array, start, end);
        //交换中间节点和起始位置
        swap(array, index, start);//此时start的下标一定是中间大的数字
        //第一次的基点
        int pivot = parttion(array, start, end);
        //递归
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //插入排序：
    public static void insterSortRange(int[] array, int begin, int end) {
        int i = 1;
        int j = i - 1;
        for (i = begin + 1; i <= end; i++) {
            int tmp = array[i];//会随着插入的元素改变
            for (j = i - 1; j >= begin; j--) {
                //插入的元素比j小
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            //插入的元素比j大
            array[j + 1] = tmp;
        }
    }

    private static int midOfThree(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[mid] > array[left]) {
                return left;
            } else if (array[mid] < array[right]) {
                return right;
            } else {
                return mid;
            }
        }
    }

    //找到位置基点
    private static int parttion1(int[] array, int left, int right) {
        int key = array[left];
        int i = left;//保存key
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }//下标一定是比key小的数据
            while (left < right && array[left] <= key) {
                left++;
            }//下标一定是比key大的数据
            swap(array, left, right);
        }
        //相遇的位置与i的位置进行交换
        swap(array, left, i);
        return left;
    }

    //挖坑法
    private static int parttion(int[] array, int left, int right) {
        int key = array[left];
        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }//下标一定是比key小的数据
            array[left] = array[right];
            while (left < right && array[left] <= key) {
                left++;
            }//下标一定是比key大的数据
            array[right] = array[left];
        }
        //相遇
        array[left] = key;
        return left;
    }

    //快排非递归
    public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int piovt = parttion(array, left, right);
        //入左
        if (piovt - 1 > left) {
            stack.push(left);
            stack.push(piovt - 1);
        }
        //入右
        if (piovt + 1 < right) {
            stack.push(piovt + 1);
            stack.push(right);
        }
        //入栈不为空,弹出左右
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            piovt = parttion(array, left, right);
            //入左
            if (piovt - 1 > left) {
                stack.push(left);
                stack.push(piovt - 1);
            }
            //入右
            if (piovt + 1 < right) {
                stack.push(piovt + 1);
                stack.push(right);
            }
        }
    }
    //归并排序
    public static void mergeSort(int[] array){
        mergeSortFunc(array, 0,array.length-1);
    }
    //左右递归
    public static void mergeSortFunc(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);//分解左边
        mergeSortFunc(array,mid+1,right);//分解右边
        merge(array,left,right,mid);//合并
    }
//合并
    private static void merge(int[] array, int left, int right, int mid) {
        int s1=left;
        int s2=mid+1;
        int[] tmpArr=new int[right-left+1];
        int k=0;//临时数组里的元素下标
        //证明两个区间都同时有数据
        while (s1 <= mid && s2 <= right) {
            if (array[s2] <= array[s1]) {
                tmpArr[k++] = array[s2++];
            } else {
                tmpArr[k++] = array[s1++];
            }
        }
        //若s1还有值
        while (s1<=mid){
            tmpArr[k++]=array[s1++];
        }
        //若s2还有值
        while (s2<=right){
            tmpArr[k++]=array[s2++];
        }
        //此时tmpArr里面一定是这个区间内有序数组了
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left]=tmpArr[i];//把右边的放进去
        }
    }
    //非递归的归并排序
    public static void mergeSortNor(int[] array){
        int gap=1;
        while (gap<array.length){
            for (int i = 0; i <array.length ; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //mid和right可能会出界
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>=array.length){
                    right=array.length-1;
                }
                //合并
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }
    //计数排序
    public static void countSort(int[] array){
        int minVal=array[0];
        int maxVal=array[0];
        //求当前数组的最大值和最小值
        for (int i = 0; i < array.length; i++) {
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
        }
        //根据最小值和最大值来确定数组的大小
        int[] count=new int[maxVal-minVal+1];
        //遍历原来的数组，开始计数
        for (int i = 0; i < array.length; i++) {
            //要减去最小值，确保数组从0下标开始
            count[array[i]-minVal]++;
        }
        //遍历计数count把元素写会array
        int index=0;//表示array数组的下标
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                array[index]=i+minVal;
                //i是从0下标开始的，为了确保数值不是从0下标开始，所以要加上
                index++;
                count[i]--;
            }
        }
    }

}